#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"

/*
    tree struct 
    {
        node    :
        parent  :
    }
    path[]={INFINITY}
    collect[]={0}

    INITIAL :
    collect[0]=1;
    对于0的每一个邻接点 w 更新path[w]=weight,parent[w]=0
    
    BEGIN:
    while(1){
        选一个未收录到MTS中的最小距离节点 p
        如果不存在这样的p 
            break;
        
        对于 p 的每一个邻接点w 距离进行更新
        if(p->w距离小于path[w]) 更新path[w]
    }
*/
void prim(Adj_Matrix G)
{
    int parent[MAX], path[MAX], collect[MAX];
    for (int i = 0; i < MAX; i++)
    {
        parent[i] = -1;
        path[i] = INFINITY;
        collect[i] = 0;
    }

    collect[0] = 1;
    int w = 0;
    while (w < G.node_num)
    {
        if (G.M[0][w] != 0 && G.M[0][w] != INFINITY)
        {
            path[w] = G.M[0][w];
            parent[w] = 0;
        }
        w++;
    }

    while (1)
    {
        int min;
        int p = INFINITY + 1;
        for (int i = 0; i < G.node_num; i++)
        {
            if (!collect[i] && path[i] < p)
            {
                p = path[i];
                min = i;
            }
        }
        if (p == INFINITY + 1)
            break;
        collect[min] = 1;
        int w = 0;
        while (w < G.node_num)
        {
            if (!collect[w] && G.M[min][w] != 0 && G.M[min][w] != INFINITY && G.M[min][w] < path[w])
            {
                path[w] = G.M[min][w];
                parent[w] = min;
            }
            w++;
        }
    }
    for (int k = 0; k < G.node_num; k++)
    {
        printf("%3d", parent[k]);
    }
}

int main()
{
    /*******************code*******************/
    Adj_Matrix G;
    creat_w(G);
    prim(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
